559. Maximum Depth of N-ary Tree

tags: Easy、Tree

Given a n-ary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

解法:

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     int numChildren;
 *     struct Node** children;
 * };
 */
int getHeight(struct Node* node, int height) {
    int max_h = 0;
    if (node == NULL) {
        return 0;
    }
    for (int i = 0; i < node->numChildren; i++) {
        int curr_h = getHeight(node->children[i], height+1);
        if (max_h < curr_h) {
            max_h = curr_h;
        }
    }
    
    return max_h + 1;
}
int maxDepth(struct Node* root) {
    return (getHeight(root, 0));
}

671. Second Minimum Node In a Binary Tree

tags: Easy、Tree

Given a non-empty special binary tree consisting of nodes with the non-negative value, where each node in this tree has exactly two or zero sub-node. If the node has two sub-nodes, then this node's value is the smaller value among its two sub-nodes. More formally, the property root.val = min(root.left.val, root.right.val) always holds.
Given such a binary tree, you need to output the second minimum value in the set made of all the nodes' value in the whole tree.
If no such second minimum value exists, output -1 instead.

解法:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int findSecMin(struct TreeNode* node, int min) {
    if (!node) {
        return -1;
    }
    if (node->val > min) {
        return node->val;
    }

    int left_min = findSecMin(node->left, min);
    int right_min = findSecMin(node->right, min);

    if (left_min == -1) {return right_min;}
    if (right_min == -1) {return left_min;}

    return left_min < right_min ? left_min : right_min;
}

int findSecondMinimumValue(struct TreeNode* root) {
    if (!root) {return -1;}
    int sec_min = findSecMin(root, root->val);
    return (sec_min == root->val) ? -1 : sec_min;
}

872. Leaf-Similar Trees

tags: Easy、Tree

Consider all the leaves of a binary tree, from left to right order, the values of those leaves form a leaf value sequence.
For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8).
Two binary trees are considered leaf-similar if their leaf value sequence is the same.
Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.

解法:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
#define MAX(a, b) ((a) > (b) ? (a) : (b))
int* trace(struct TreeNode* node, int* array, int* index) {
    if (!node) {
        return NULL;
    }

    trace(node->left, array, index);
    trace(node->right, array, index);

    if ((node->left == NULL) && (node->right == NULL)) {
        array[(*index)++] = node->val;
    }
    return array;
    
}
bool leafSimilar(struct TreeNode* root1, struct TreeNode* root2) {
    int* array1 = (int*)malloc(200 * sizeof(int));
    int* array2 = (int*)malloc(200 * sizeof(int));
    int index1 = 0;
    int index2 = 0;
    trace(root1, array1, &index1);
    trace(root2, array2, &index2);

    for (int i = 0; i < MAX(index1, index2); i++) {
        if (array1[i] != array2[i]) {
            return false;
        }
    }
    return true;
}

1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree

tags: Easy、Tree

Given two binary trees original and cloned and given a reference to a node target in the original tree.
The cloned tree is a copy of the original tree.
Return a reference to the same node in the cloned tree.
Note that you are not allowed to change any of the two trees or the target node and the answer must be a reference to a node in the cloned tree.

解法1:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* trace(TreeNode* ori, int val) {
        if(!ori) {return NULL;}
        if (ori->val == val) {
            return ori;
        }

        TreeNode* left_node = trace(ori->left, val);
        if (left_node) {return left_node;}
        TreeNode* right_node = trace(ori->right, val);

        return trace(ori->right, val);
    }
    TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
        return trace(cloned, target->val);
    }
};

解法2:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
        if (!cloned) {return NULL;}
        if (cloned->val == target->val) {return cloned;}
        cloned->left = getTargetCopy(original, cloned->left, target);
        if (cloned->left != NULL) {
            return cloned->left;
        }
        return getTargetCopy(original, cloned->right, target);
    }
};